home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
EnigmA Amiga Run 1999 March
/
EnigmA AMIGA RUN 35 (1999)(G.R. Edizioni)(IT)[!][issue 1999-03].iso
/
earcd
/
-archivi
/
-recent2
/
amhelios.lha
/
AmHelios
/
oct_quan.cpp
< prev
next >
Wrap
C/C++ Source or Header
|
1997-07-13
|
8KB
|
327 lines
////////////////////////////////////////////////////////////
//
// OCT_QUAN.CPP - Octree Color Quantization Class
//
// Version: 1.03A
//
// History: 94/08/23 - Version 1.00A release.
// 94/11/10 - Modified InsertNode to properly
// mark nodes as reducible.
// 94/11/11 - Version 1.00B release.
// 94/11/27 - Converted to MS-Windows
// environment.
// 94/12/16 - Version 1.01A release.
// 95/02/05 - Version 1.02A release.
// 95/07/21 - Version 1.02B release.
// 96/02/14 - Version 1.02C release.
// 96/04/01 - Version 1.03A release.
//
// Compilers: Microsoft Visual C/C++ Professional V1.5
// Borland C++ Version 4.5
//
// Author: Ian Ashdown, P.Eng.
// byHeart Software Limited
// 620 Ballantree Road
// West Vancouver, B.C.
// Canada V7S 1W3
// Tel. (604) 922-6148
// Fax. (604) 987-7621
//
// Copyright 1994-1996 byHeart Software Limited
//
// The following source code has been derived from:
//
// Ashdown, I. 1994. Radiosity: A Programmer's
// Perspective. New York, NY: John Wiley & Sons.
//
// It may be freely copied, redistributed, and/or modified
// for personal use ONLY, as long as the copyright notice
// is included with all source code files.
//
////////////////////////////////////////////////////////////
#include "oct_quan.h"
// Write device-independent bitmap (DIB) to file
// Quantize 24-bit RGB color bitmap
BOOL OctQuant::Quantize()
{
if (BuildTree() == FALSE) // Build octree
return FALSE;
// Initialize number of quantized colors
num_colors = 0;
// Set color palette entries
FillPalette(proot, &num_colors);
// Map 24-bit RGB colors to 8-bit color palette entries
MapColors();
DeleteTree(); // Delete octree
return TRUE;
}
void OctQuant::DeleteTree() // Delete octree
{
int i; // Loop index
// Clear the reducible node list pointers
for (i = 0; i < leaf_level; i++)
prnl[i] = NULL;
if (proot != NULL) // Release octree nodes
{
DeleteNode(proot);
proot = NULL;
}
// Reset octree leaf level
leaf_level = O_MaxDepth + 1;
}
BOOL OctQuant::BuildTree() // Build octree
{
int row; // Row counter
int col; // Column counter
BOOL status = TRUE; // Return status
ColorRGB color; // Pixel color
// Allocate octree root node
if ((proot = MakeNode(0)) == NULL)
status = FALSE;
// Build the octree
if (status == TRUE)
{
for (row = 0; row < height; row++)
{
for (col = 0; col < width; col++)
{
GetPixel(col, row, &color);
// Insert pixel color into octree
if (InsertNode(proot, color) == FALSE)
{
DeleteNode(proot); // Delete the octree
status = FALSE;
break;
}
// Reduce octree if too many colors
if (num_leaf > max_colors)
ReduceTree();
}
if (status == FALSE)
break;
}
}
return status;
}
// Recursively delete octree nodes
void OctQuant::DeleteNode( OctNode *pn )
{
int i; // Loop index
OctNode *pc; // Child node pointer
if (pn == NULL)
return;
if (pn->IsLeaf() == FALSE)
{
// Delete child nodes
for (i = 0; i < 8; i++)
{
if ((pc = pn->GetChild(i)) != NULL)
{
DeleteNode(pc);
pn->SetChild(i, NULL);
pn->DecNumChild();
}
}
}
else
num_leaf--;
delete pn;
}
// Set color palette entries
void OctQuant::FillPalette( OctNode *pn, int *pindex )
{
int i; // Loop index
// Perform recursive depth-first traversal of octree
if (pn != NULL)
{
if ((pn->IsLeaf() == TRUE) || pn->GetLevel() ==
leaf_level)
{
// Set color palette entry
palette[*pindex].SetRed(pn->GetColor().GetRed());
palette[*pindex].SetGreen(pn->GetColor().GetGreen());
palette[*pindex].SetBlue(pn->GetColor().GetBlue());
// Set node color palette index
pn->SetIndex(*pindex);
// Advance to next color palette entry
*pindex = *pindex + 1;
}
else
{
// Visit child nodes
for (i = 0; i < 8; i++)
FillPalette(pn->GetChild(i), pindex);
}
}
}
// Get next reducible node pointer
OctNode *OctQuant::GetReducible()
{
int new_level; // New reducible node level
OctNode *prn; // Reducible node pointer
OctNode *pscn = NULL; // Smallest pixel count node
OctNode *pnext; // Next node
OctNode *pprev; // Previous node
new_level = leaf_level - 1;
// Find lowest reducible node level
while (prnl[new_level] == NULL)
new_level--;
// Find node with smallest pixel count
prn = prnl[new_level];
while (prn != NULL)
{
if (pscn == NULL)
pscn = prn;
else if (prn->GetCount() < pscn->GetCount())
pscn = prn;
prn = prn->GetNext();
}
// Remove node from reducible list
pnext = pscn->GetNext();
pprev = pscn->GetPrev();
if (pprev == NULL)
{
prnl[new_level] = pnext;
if (pnext != NULL)
pnext->SetPrev(NULL);
}
else
{
pprev->SetNext(pnext);
if (pnext != NULL)
pnext->SetPrev(pprev);
}
pscn->SetNext(NULL);
pscn->SetPrev(NULL);
pscn->SetMark(FALSE);
return pscn;
}
void OctQuant::ReduceTree() // Reduce octree
{
int i; // Loop index
OctNode *pn; // Node pointer
OctNode *pc; // Child node pointer
pn = GetReducible(); // Get next reducible node
// Delete children
for (i = 0; i < 8; i++)
{
if ((pc = pn->GetChild(i)) != NULL)
{
DeleteNode(pc);
pn->SetChild(i, NULL);
pn->DecNumChild();
}
}
pn->SetLeaf(TRUE); // Mark node as leaf
num_leaf++; // Increment leaf count
// Update reduction and leaf levels
if (pn->GetLevel() < (leaf_level - 1))
leaf_level = pn->GetLevel() + 1;
}
// Insert node into octree
BOOL OctQuant::InsertNode( OctNode *pn, ColorRGB &c )
{
int c_index; // Child index
int level; // Node level
BOOL status = TRUE; // Return status
OctNode *pc; // Child node pointer
level = pn->GetLevel(); // Get node level
pn->AddColor(c); // Add RGB color to node
if (pn->IsLeaf() == FALSE && level < leaf_level)
{
// Find child node
c_index = pn->FindChild(c);
if ((pc = pn->GetChild(c_index)) == NULL)
{
// Allocate child node
if ((pc = MakeNode(level + 1)) == NULL)
return FALSE;
// Set child node pointer
pn->SetChild(c_index, pc);
pn->IncNumChild(); // Increment child count
}
if ((pn->GetNumChild() > 1) && (pn->IsMark() == FALSE))
{
// Mark node as candidate for reduction
MakeReducible(pn);
}
// Insert child node into octree
status = InsertNode(pc, c);
}
return status;
}
// Map 24-bit RGB colors to 8-bit color palette entries
void OctQuant::MapColors()
{
int row; // Row counter
int col; // Column counter
BYTE qcolor; // Quantized pixel color
ColorRGB color; // 24-bit RGB color
// Quantize the bitmap colors
for (row = 0; row < height; row++)
{
for (col = 0; col < width; col++)
{
// Get 24-bit RGB pixel color
GetPixel(col, row, &color);
// Get color palette index
qcolor = QuantizeColor(proot, color);
// Set 8-bit palette pixel color
SetPalPixel(col, row, qcolor);
}
}
}